home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Internet Tools 1993 July / Internet Tools.iso / RockRidge / ip / trace / tcpdump-2.2.1 / optimize.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-07-18  |  35.9 KB  |  1,872 lines
  1. /*
  2.  * Copyright (c) 1988-1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that: (1) source code distributions
  7.  * retain the above copyright notice and this paragraph in its entirety, (2)
  8.  * distributions including binary code include the above copyright notice and
  9.  * this paragraph in its entirety in the documentation or other materials
  10.  * provided with the distribution, and (3) all advertising materials mentioning
  11.  * features or use of this software display the following acknowledgement:
  12.  * ``This product includes software developed by the University of California,
  13.  * Lawrence Berkeley Laboratory and its contributors.'' Neither the name of
  14.  * the University nor the names of its contributors may be used to endorse
  15.  * or promote products derived from this software without specific prior
  16.  * written permission.
  17.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  18.  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  19.  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  20.  *
  21.  *  Optimization module for tcpdump intermediate representation.
  22.  */
  23. #ifndef lint
  24. static char rcsid[] =
  25.     "@(#) $Header: optimize.c,v 1.35 91/07/18 09:27:55 mccanne Exp $ (LBL)";
  26. #endif
  27.  
  28. #include <stdio.h>
  29. #include <sys/types.h>
  30.  
  31. #include <sys/time.h>
  32. #include <net/bpf.h>
  33.  
  34. #include "interface.h"
  35. #include "gencode.h"
  36.  
  37. #define A_ATOM BPF_MEMWORDS
  38. #define X_ATOM (BPF_MEMWORDS+1)
  39.  
  40. #define NOP -1
  41.  
  42. /*
  43.  * This define is used to represent *both* the accumulator and
  44.  * x register in use-def computations.
  45.  * Currently, the use-def code assumes only one definition per instruction.
  46.  */
  47. #define AX_ATOM N_ATOMS
  48.  
  49. /*
  50.  * A flag to indicate that further optimization is needed.
  51.  * Iterative passes are continued until a given pass yields no 
  52.  * branch movement.
  53.  */
  54. static int done;
  55.  
  56. /*
  57.  * A block is marked if only if its mark equals the current mark.
  58.  * Rather than traverse the code array, marking each item, 'cur_mark' is
  59.  * incremented.  This automatically makes each element unmarked.
  60.  */
  61. static int cur_mark;
  62. #define isMarked(p) ((p)->mark == cur_mark)
  63. #define unMarkAll() cur_mark += 1
  64. #define Mark(p) ((p)->mark = cur_mark)
  65.  
  66. static void opt_init();
  67. static void opt_cleanup();
  68.  
  69. static void make_marks();
  70. static void mark_code();
  71.  
  72. static void intern_blocks();
  73.  
  74. static int eq_slist();
  75.  
  76. static int n_blocks;
  77. struct block **blocks;
  78. static int n_edges;
  79. struct edge **edges;
  80.  
  81. /*
  82.  * A bit vector set representation of the dominators.  
  83.  * We round up the set size to the next power of two.  
  84.  */
  85. static int nodewords;
  86. static int edgewords;
  87. struct block **levels;
  88. u_long *space;
  89. #define BITS_PER_WORD (8*sizeof(u_long))
  90. /*
  91.  * True if a is in uset {p}
  92.  */
  93. #define SET_MEMBER(p, a) \
  94. ((p)[(unsigned)(a) / BITS_PER_WORD] & (1 << ((unsigned)(a) % BITS_PER_WORD)))
  95.  
  96. /*
  97.  * Add 'a' to uset p.
  98.  */
  99. #define SET_INSERT(p, a) \
  100. (p)[(unsigned)(a) / BITS_PER_WORD] |= (1 << ((unsigned)(a) % BITS_PER_WORD))
  101.  
  102. /*
  103.  * Delete 'a' from uset p.
  104.  */
  105. #define SET_DELETE(p, a) \
  106. (p)[(unsigned)(a) / BITS_PER_WORD] &= ~(1 << ((unsigned)(a) % BITS_PER_WORD))
  107.  
  108. /*
  109.  * a := a intersect b
  110.  */
  111. #define SET_INTERSECT(a, b, n)\
  112. {\
  113.     register u_long *_x = a, *_y = b;\
  114.     register int _n = n;\
  115.     while (--_n >= 0) *_x++ &= *_y++;\
  116. }
  117.  
  118. /*
  119.  * a := a - b
  120.  */
  121. #define SET_SUBTRACT(a, b, n)\
  122. {\
  123.     register u_long *_x = a, *_y = b;\
  124.     register int _n = n;\
  125.     while (--_n >= 0) *_x++ &=~ *_y++;\
  126. }
  127.  
  128. /*
  129.  * a := a union b
  130.  */
  131. #define SET_UNION(a, b, n)\
  132. {\
  133.     register u_long *_x = a, *_y = b;\
  134.     register int _n = n;\
  135.     while (--_n >= 0) *_x++ |= *_y++;\
  136. }
  137.  
  138. static uset all_dom_sets;
  139. static uset all_closure_sets;
  140. static uset all_edge_sets;
  141.  
  142. #ifndef MAX
  143. #define MAX(a,b) ((a)>(b)?(a):(b))
  144. #endif
  145.  
  146. static void
  147. find_levels_r(b)
  148.     struct block *b;
  149. {
  150.     int level;
  151.  
  152.     if (isMarked(b))
  153.         return;
  154.  
  155.     Mark(b);
  156.     b->link = 0;
  157.  
  158.     if (JT(b)) {
  159.         find_levels_r(JT(b));
  160.         find_levels_r(JF(b));
  161.         level = MAX(JT(b)->level, JF(b)->level) + 1;
  162.     } else
  163.         level = 0;
  164.     b->level = level;
  165.     b->link = levels[level];
  166.     levels[level] = b;
  167. }
  168.  
  169. /*
  170.  * Level graph.  The levels go from 0 at the leaves to 
  171.  * N_LEVELS at the root.  The levels[] array points to the
  172.  * first node of the level list, whose elements are linked
  173.  * with the 'link' field of the struct block.
  174.  */
  175. static void
  176. find_levels(root)
  177.     struct block *root;
  178. {
  179.     bzero((char *)levels, n_blocks * sizeof(*levels));
  180.     unMarkAll();
  181.     find_levels_r(root);
  182. }
  183.  
  184. /* 
  185.  * Find dominator relationships.
  186.  * Assumes graph has been leveled.
  187.  */
  188. static void
  189. find_dom(root)
  190.     struct block *root;
  191. {
  192.     int i;
  193.     struct block *b;
  194.     u_long *x;
  195.  
  196.     /*
  197.      * Initialize sets to contain all nodes.
  198.      */
  199.     x = all_dom_sets;
  200.     i = n_blocks * nodewords;
  201.     while (--i >= 0)
  202.         *x++ = ~0;
  203.     /* Root starts off empty. */
  204.     for (i = nodewords; --i >= 0;)
  205.         root->dom[i] = 0;
  206.     
  207.     /* root->level is the highest level no found. */
  208.     for (i = root->level; i >= 0; --i) {
  209.         for (b = levels[i]; b; b = b->link) {
  210.             SET_INSERT(b->dom, b->id);
  211.             if (JT(b) == 0)
  212.                 continue;
  213.             SET_INTERSECT(JT(b)->dom, b->dom, nodewords);
  214.             SET_INTERSECT(JF(b)->dom, b->dom, nodewords);
  215.         }
  216.     }
  217. }
  218.  
  219. static void
  220. propedom(ep)
  221.     struct edge *ep;
  222. {
  223.     SET_INSERT(ep->edom, ep->id);
  224.     if (ep->succ) {
  225.         SET_INTERSECT(ep->succ->et.edom, ep->edom, edgewords);
  226.         SET_INTERSECT(ep->succ->ef.edom, ep->edom, edgewords);
  227.     }
  228. }
  229.  
  230. /* 
  231.  * Compute edge dominators.
  232.  * Assumes graph has been leveled and predecessors estabished.
  233.  */
  234. static void
  235. find_edom(root)
  236.     struct block *root;
  237. {
  238.     int i;
  239.     uset x;
  240.     struct block *b;
  241.  
  242.     x = all_edge_sets;
  243.     for (i = n_edges * edgewords; --i >= 0; )
  244.         x[i] = ~0;
  245.  
  246.     /* root->level is the highest level no found. */
  247.     bzero(root->et.edom, edgewords * sizeof(*(uset)0));
  248.     bzero(root->ef.edom, edgewords * sizeof(*(uset)0));
  249.     for (i = root->level; i >= 0; --i) {
  250.         for (b = levels[i]; b != 0; b = b->link) {
  251.             propedom(&b->et);
  252.             propedom(&b->ef);
  253.         }
  254.     }
  255. }
  256.  
  257. /* 
  258.  * Find the backwards transitive closure of the flow graph.  These sets
  259.  * are backwards in the sense that we find the set of nodes that reach
  260.  * a given node, not the set of nodes that can be reached by a node.
  261.  *
  262.  * Assumes graph has been leveled.
  263.  */
  264. static void
  265. find_closure(root)
  266.     struct block *root;
  267. {
  268.     int i;
  269.     struct block *b;
  270.  
  271.     /*
  272.      * Initialize sets to contain no nodes.
  273.      */
  274.     bzero((char *)all_closure_sets, 
  275.           n_blocks * nodewords * sizeof(*all_closure_sets));
  276.     
  277.     /* root->level is the highest level no found. */
  278.     for (i = root->level; i >= 0; --i) {
  279.         for (b = levels[i]; b; b = b->link) {
  280.             SET_INSERT(b->closure, b->id);
  281.             if (JT(b) == 0)
  282.                 continue;
  283.             SET_UNION(JT(b)->closure, b->closure, nodewords);
  284.             SET_UNION(JF(b)->closure, b->closure, nodewords);
  285.         }
  286.     }
  287. }
  288.  
  289. /* 
  290.  * Return the register number that is used by s.  If A and X are both
  291.  * used, return AX_ATOM.  If no register is used, return -1.
  292.  * 
  293.  * The implementation should probably change to an array access.
  294.  */
  295. static int
  296. atomuse(s)
  297.     struct stmt *s;
  298. {
  299.     register int c = s->code;
  300.  
  301.     if (c == NOP)
  302.         return -1;
  303.  
  304.     switch (BPF_CLASS(c)) {
  305.  
  306.     case BPF_RET:
  307.         return (BPF_RVAL(c) == BPF_A) ? A_ATOM : 
  308.             (BPF_RVAL(c) == BPF_X) ? X_ATOM : -1;
  309.  
  310.     case BPF_LD:
  311.     case BPF_LDX:
  312.         return (BPF_MODE(c) == BPF_IND) ? X_ATOM :
  313.             (BPF_MODE(c) == BPF_MEM) ? s->k : -1;
  314.  
  315.     case BPF_ST:
  316.         return A_ATOM;
  317.  
  318.     case BPF_STX:
  319.         return X_ATOM;
  320.  
  321.     case BPF_JMP:
  322.     case BPF_ALU:
  323.         if (BPF_SRC(c) == BPF_X)
  324.             return AX_ATOM;
  325.         return A_ATOM;
  326.  
  327.     case BPF_MISC:
  328.         return BPF_MISCOP(c) == BPF_TXA ? X_ATOM : A_ATOM;
  329.     }
  330.     abort();
  331.     /* NOTREACHED */
  332. }
  333.  
  334. /* 
  335.  * Return the register number that is defined by 's'.  We assume that
  336.  * a single stmt cannot define more than one register.  If no register
  337.  * is defined, return -1.
  338.  *
  339.  * The implementation should probably change to an array access.
  340.  */
  341. static int
  342. atomdef(s)
  343.     struct stmt *s;
  344. {
  345.     if (s->code == NOP)
  346.         return -1;
  347.  
  348.     switch (BPF_CLASS(s->code)) {
  349.  
  350.     case BPF_LD:
  351.     case BPF_ALU:
  352.         return A_ATOM;
  353.  
  354.     case BPF_LDX:
  355.         return X_ATOM;
  356.  
  357.     case BPF_ST:
  358.     case BPF_STX:
  359.         return s->k;
  360.  
  361.     case BPF_MISC:
  362.         return BPF_MISCOP(s->code) == BPF_TAX ? X_ATOM : A_ATOM;
  363.     }
  364.     return -1;
  365. }
  366.  
  367. static void
  368. compute_local_ud(b)
  369.     struct block *b;
  370. {
  371.     struct slist *s;
  372.     atomset def = 0, use = 0, kill = 0;
  373.     int atom;
  374.  
  375.     for (s = b->stmts; s; s = s->next) {
  376.         if (s->s.code == NOP)
  377.             continue;
  378.         atom = atomuse(&s->s);
  379.         if (atom >= 0) {
  380.             if (atom == AX_ATOM) {
  381.                 if (!ATOMELEM(def, X_ATOM))
  382.                     use |= ATOMMASK(X_ATOM);
  383.                 if (!ATOMELEM(def, A_ATOM))
  384.                     use |= ATOMMASK(A_ATOM);
  385.             }
  386.             else if (atom < N_ATOMS) {
  387.                 if (!ATOMELEM(def, atom))
  388.                     use |= ATOMMASK(atom);
  389.             }
  390.             else
  391.                 abort();
  392.         }
  393.         atom = atomdef(&s->s);
  394.         if (atom >= 0) {
  395.             if (!ATOMELEM(atom, use))
  396.                 kill |= ATOMMASK(atom);
  397.             def |= ATOMMASK(atom);
  398.         }
  399.     }
  400.     if (!ATOMELEM(def, A_ATOM) && BPF_CLASS(b->s.code) == BPF_JMP)
  401.         use |= ATOMMASK(A_ATOM);
  402.         
  403.     b->def = def;
  404.     b->kill = kill;
  405.     b->in_use = use;
  406. }
  407.  
  408. /*
  409.  * Assume graph is already leveled.
  410.  */
  411. static void
  412. find_ud(root)
  413.     struct block *root;
  414. {
  415.     int i, maxlevel;
  416.     struct block *p;
  417.  
  418.     /*
  419.      * root->level is the highest level no found;
  420.      * count down from there.
  421.      */
  422.     maxlevel = root->level;
  423.     for (i = maxlevel; i >= 0; --i)
  424.         for (p = levels[i]; p; p = p->link) {
  425.             compute_local_ud(p);
  426.             p->out_use = 0;
  427.         }
  428.  
  429.     for (i = 1; i <= maxlevel; ++i) {
  430.         for (p = levels[i]; p; p = p->link) {
  431.             p->out_use |= JT(p)->in_use | JF(p)->in_use;
  432.             p->in_use |= p->out_use &~ p->kill;
  433.         }
  434.     }
  435. }
  436.  
  437. /* 
  438.  * These data structures are used in a Cocke and Shwarz style
  439.  * value numbering scheme.  Since the flowgraph is acyclic,
  440.  * exit values can be propagated from a node's predecessors
  441.  * provided it is uniquely defined.
  442.  */
  443. struct valnode {
  444.     int code;
  445.     long v0, v1;
  446.     long val;
  447.     struct valnode *next;
  448. };
  449.     
  450. #define MODULUS 213
  451. static struct valnode *hashtbl[MODULUS];
  452. static int curval;
  453. static int maxval;
  454.  
  455. /* Integer constants mapped with the load immediate opcode. */
  456. #define K(i) F(BPF_LD|BPF_IMM|BPF_W, i, 0L)
  457.  
  458. struct vmapinfo {
  459.     int is_const;
  460.     long const_val;
  461. };
  462.  
  463. struct vmapinfo *vmap;
  464. struct valnode *vnode_base;
  465. struct valnode *next_vnode;
  466.  
  467. static void
  468. init_val()
  469. {
  470.     curval = 0;
  471.     next_vnode = vnode_base;
  472.     bzero((char *)vmap, maxval * sizeof(*vmap));
  473.     bzero((char *)hashtbl, sizeof hashtbl);
  474. }
  475.  
  476. /* Because we really don't have an IR, this stuff is a little messy. */
  477. static long
  478. F(code, v0, v1)
  479.     int code;
  480.     long v0, v1;
  481. {
  482.     u_int hash;
  483.     int val;
  484.     struct valnode *p;
  485.  
  486.     hash = (u_int)code ^ (v0 << 4) ^ (v1 << 8);
  487.     hash %= MODULUS;
  488.  
  489.     for (p = hashtbl[hash]; p; p = p->next)
  490.         if (p->code == code && p->v0 == v0 && p->v1 == v1)
  491.             return p->val;
  492.  
  493.     val = ++curval;
  494.     if (BPF_MODE(code) == BPF_IMM && 
  495.         (BPF_CLASS(code) == BPF_LD || BPF_CLASS(code) == BPF_LDX)) {
  496.         vmap[val].const_val = v0;
  497.         vmap[val].is_const = 1;
  498.     }
  499.     p = next_vnode++;
  500.     p->val = val;
  501.     p->code = code;
  502.     p->v0 = v0;
  503.     p->v1 = v1;
  504.     p->next = hashtbl[hash];
  505.     hashtbl[hash] = p;
  506.  
  507.     return val;
  508. }
  509.  
  510. static inline void
  511. vstore(s, valp, newval, alter)
  512.     struct stmt *s;
  513.     long *valp;
  514.     long newval;
  515.     int alter;
  516. {
  517.     if (alter && *valp == newval)
  518.         s->code = NOP;
  519.     else
  520.         *valp = newval;
  521. }
  522.  
  523. static void
  524. fold_op(s, v0, v1)
  525.     struct stmt *s;
  526.     long v0, v1;
  527. {
  528.     long a, b;
  529.  
  530.     a = vmap[v0].const_val;
  531.     b = vmap[v1].const_val;
  532.  
  533.     switch (BPF_OP(s->code)) {
  534.     case BPF_ADD:
  535.         a += b;
  536.         break;
  537.  
  538.     case BPF_SUB:
  539.         a -= b;
  540.         break;
  541.  
  542.     case BPF_MUL:
  543.         a *= b;
  544.         break;
  545.  
  546.     case BPF_DIV:
  547.         if (b == 0)
  548.             error("division by zero");
  549.         a /= b;
  550.         break;
  551.  
  552.     case BPF_AND:
  553.         a &= b;
  554.         break;
  555.  
  556.     case BPF_OR:
  557.         a |= b;
  558.         break;
  559.  
  560.     case BPF_LSH:
  561.         a <<= b;
  562.         break;
  563.  
  564.     case BPF_RSH:
  565.         a >>= b;
  566.         break;
  567.  
  568.     case BPF_NEG:
  569.         a = -a;
  570.         break;
  571.  
  572.     default:
  573.         abort();
  574.     }
  575.     s->k = a;
  576.     s->code = BPF_LD|BPF_IMM;
  577.     done = 0;
  578. }
  579.  
  580. static inline struct slist *
  581. this_op(s)
  582.     struct slist *s;
  583. {
  584.     while (s != 0 && s->s.code == NOP)
  585.         s = s->next;
  586.     return s;
  587. }
  588.  
  589. static void
  590. opt_not(b)
  591.     struct block *b;
  592. {
  593.     struct block *tmp = JT(b);
  594.  
  595.     JT(b) = JF(b);
  596.     JF(b) = tmp;
  597. }
  598.  
  599. static void
  600. opt_peep(b)
  601.     struct block *b;
  602. {
  603.     struct slist *s;
  604.     struct slist *next, *last;
  605.     int val;
  606.     long v;
  607.  
  608.     s = b->stmts;
  609.     if (s == 0)
  610.         return;
  611.  
  612.     last = s;
  613.     while (1) {
  614.         s = this_op(s);
  615.         if (s == 0)
  616.             break;
  617.         next = this_op(s->next);
  618.         if (next == 0)
  619.             break;
  620.         last = next;
  621.  
  622.         /*
  623.          * st  M[k]    -->    st  M[k]
  624.          * ldx M[k]        tax
  625.          */
  626.         if (s->s.code == BPF_ST &&
  627.             next->s.code == (BPF_LDX|BPF_MEM) &&
  628.             s->s.k == next->s.k) {
  629.             done = 0;
  630.             next->s.code = BPF_MISC|BPF_TAX;
  631.         }
  632.         /*
  633.          * ld  #k    -->    ldx  #k
  634.          * tax            txa
  635.          */
  636.         if (s->s.code == (BPF_LD|BPF_IMM) &&
  637.             next->s.code == (BPF_MISC|BPF_TAX)) {
  638.             s->s.code = BPF_LDX|BPF_IMM;
  639.             next->s.code = BPF_MISC|BPF_TXA;
  640.             done = 0;
  641.         }
  642.         /*
  643.          * This is an ugly special case, but it happens
  644.          * when you say tcp[k] or udp[k] where k is a constant.
  645.          */
  646.         if (s->s.code == (BPF_LD|BPF_IMM)) {
  647.             struct slist *add, *tax, *ild;
  648.  
  649.             /*
  650.              * Check that X isn't used on exit from this
  651.              * block (which the optimizer might cause).
  652.              * We know the code generator won't generate
  653.              * any local dependencies.
  654.              */
  655.             if (ATOMELEM(b->out_use, X_ATOM))
  656.                 break;
  657.  
  658.             if (next->s.code != (BPF_LDX|BPF_MSH|BPF_B))
  659.                 add = next;
  660.             else
  661.                 add = this_op(next->next);
  662.             if (add == 0 || add->s.code != (BPF_ALU|BPF_ADD|BPF_X))
  663.                 break;
  664.  
  665.             tax = this_op(add->next);
  666.             if (tax == 0 || tax->s.code != (BPF_MISC|BPF_TAX))
  667.                 break;
  668.  
  669.             ild = this_op(tax->next);
  670.             if (ild == 0 || BPF_CLASS(ild->s.code) != BPF_LD || 
  671.                 BPF_MODE(ild->s.code) != BPF_IND)
  672.                 break;
  673.             /* 
  674.              * XXX We need to check that X is not
  675.              * subsequently used.  We know we can eliminate the
  676.              * accumulator modifications since it is defined
  677.              * by the last stmt of this sequence.
  678.              *
  679.              * We want to turn this sequence:
  680.              *
  681.              * (004) ldi     #0x2        {s}
  682.              * (005) ldxms   [14]        {next}  -- optional
  683.              * (006) addx            {add}
  684.              * (007) tax            {tax}
  685.              * (008) ild     [x+0]        {ild}
  686.              *
  687.              * into this sequence:
  688.              *
  689.              * (004) nop
  690.              * (005) ldxms   [14]
  691.              * (006) nop
  692.              * (007) nop
  693.              * (008) ild     [x+2]
  694.              *
  695.              */
  696.             ild->s.k += s->s.k;
  697.             s->s.code = NOP;
  698.             add->s.code = NOP;
  699.             tax->s.code = NOP;
  700.             done = 0;
  701.         }
  702.         s = next;
  703.     }
  704.     /*
  705.      * If we have a subtract to do a comparsion, and the X register
  706.      * is a known constant, we can merge this value into the 
  707.      * comparison.
  708.      */
  709.     if (last->s.code == (BPF_ALU|BPF_SUB|BPF_X) &&
  710.         !ATOMELEM(b->out_use, A_ATOM)) {
  711.         val = b->val[X_ATOM];
  712.         if (vmap[val].is_const) {
  713.             b->s.k += vmap[val].const_val;
  714.             last->s.code = NOP;
  715.             done = 0;
  716.         } else if (b->s.k == 0) {
  717.             /*
  718.              * sub x  ->    nop
  719.              * j  #0    j  x
  720.              */
  721.             last->s.code = NOP;
  722.             b->s.code = BPF_CLASS(b->s.code) | BPF_OP(b->s.code) |
  723.                 BPF_X;
  724.             done = 0;
  725.         }
  726.     }
  727.     /*
  728.      * Likewise, a constant subtract can be simplified.
  729.      */
  730.     else if (last->s.code == (BPF_ALU|BPF_SUB|BPF_K) &&
  731.          !ATOMELEM(b->out_use, A_ATOM)) {
  732.         b->s.k += last->s.k;
  733.         last->s.code = NOP;
  734.         done = 0;
  735.     }
  736.     /*
  737.      * and #k    nop
  738.      * jeq #0  ->    jset #k
  739.      */
  740.     if (last->s.code == (BPF_ALU|BPF_AND|BPF_K) &&
  741.         !ATOMELEM(b->out_use, A_ATOM) && b->s.k == 0) {
  742.         b->s.k = last->s.k;
  743.         b->s.code = BPF_JMP|BPF_K|BPF_JSET;
  744.         last->s.code = NOP;
  745.         done = 0;
  746.         opt_not(b);
  747.     }
  748.     /*
  749.      * If the accumulator is a known constant, we can compute the
  750.      * comparison result.
  751.      */
  752.     val = b->val[A_ATOM];
  753.     if (vmap[val].is_const && BPF_SRC(b->s.code) == BPF_K) {
  754.         v = vmap[val].const_val;
  755.         switch (BPF_OP(b->s.code)) {
  756.  
  757.         case BPF_JEQ:
  758.             v = v == b->s.k;
  759.             break;
  760.  
  761.         case BPF_JGT:
  762.             v = v > b->s.k;
  763.             break;
  764.  
  765.         case BPF_JGE:
  766.             v = v >= b->s.k;
  767.             break;
  768.  
  769.         case BPF_JSET:
  770.             v &= b->s.k;
  771.             break;
  772.  
  773.         default:
  774.             abort();
  775.         }
  776.         if (JF(b) != JT(b))
  777.             done = 0;
  778.         if (v)
  779.             JF(b) = JT(b);
  780.         else
  781.             JT(b) = JF(b);
  782.     }
  783. }
  784.  
  785. /*
  786.  * Compute the symbolic value of expression of 's', and update
  787.  * anything it defines in the value table 'val'.  If 'alter' is true,
  788.  * do various optimizations.  This code would be cleaner if symblic
  789.  * evaluation and code transformations weren't folded together.
  790.  */
  791. static void
  792. opt_stmt(s, val, alter)
  793.     struct stmt *s;
  794.     long val[];
  795.     int alter;
  796. {
  797.     int op;
  798.     long v;
  799.  
  800.     switch (s->code) {
  801.  
  802.     case BPF_LD|BPF_ABS|BPF_W:
  803.     case BPF_LD|BPF_ABS|BPF_H:
  804.     case BPF_LD|BPF_ABS|BPF_B:
  805.         v = F(s->code, s->k, 0L);
  806.         vstore(s, &val[A_ATOM], v, alter);
  807.         break;
  808.  
  809.     case BPF_LD|BPF_IND|BPF_W:
  810.     case BPF_LD|BPF_IND|BPF_H:
  811.     case BPF_LD|BPF_IND|BPF_B:
  812.         v = val[X_ATOM];
  813.         if (alter && vmap[v].is_const) {
  814.             s->code = BPF_LD|BPF_ABS|BPF_SIZE(s->code);
  815.             s->k += vmap[v].const_val;
  816.             v = F(s->code, s->k, 0L);
  817.             done = 0;
  818.         }
  819.         else
  820.             v = F(s->code, s->k, v);
  821.         vstore(s, &val[A_ATOM], v, alter);
  822.         break;
  823.         
  824.     case BPF_LD|BPF_LEN:
  825.         v = F(s->code, 0L, 0L);
  826.         vstore(s, &val[A_ATOM], v, alter);
  827.         break;
  828.  
  829.     case BPF_LD|BPF_IMM:
  830.         v = K(s->k);
  831.         vstore(s, &val[A_ATOM], v, alter);
  832.         break;
  833.  
  834.     case BPF_LDX|BPF_IMM:
  835.         v = K(s->k);
  836.         vstore(s, &val[X_ATOM], v, alter);
  837.         break;
  838.  
  839.     case BPF_LDX|BPF_MSH|BPF_B:
  840.         v = F(s->code, s->k, 0L);
  841.         vstore(s, &val[X_ATOM], v, alter);
  842.         break;
  843.  
  844.     case BPF_ALU|BPF_NEG:
  845.         if (alter && vmap[val[A_ATOM]].is_const) {
  846.             s->code = BPF_LD|BPF_IMM;
  847.             s->k = -vmap[val[A_ATOM]].const_val;
  848.             val[A_ATOM] = K(s->k);
  849.         }
  850.         else
  851.             val[A_ATOM] = F(s->code, val[A_ATOM], 0L);
  852.         break;
  853.  
  854.     case BPF_ALU|BPF_ADD|BPF_K:
  855.     case BPF_ALU|BPF_SUB|BPF_K:
  856.     case BPF_ALU|BPF_MUL|BPF_K:
  857.     case BPF_ALU|BPF_DIV|BPF_K:
  858.     case BPF_ALU|BPF_AND|BPF_K:
  859.     case BPF_ALU|BPF_OR|BPF_K:
  860.     case BPF_ALU|BPF_LSH|BPF_K:
  861.     case BPF_ALU|BPF_RSH|BPF_K:
  862.         op = BPF_OP(s->code);
  863.         if (alter) {
  864.             if (s->k == 0) {
  865.                 if (op == BPF_ADD || op == BPF_SUB ||
  866.                     op == BPF_LSH || op == BPF_RSH ||
  867.                     op == BPF_OR) {
  868.                     s->code = NOP;
  869.                     break;
  870.                 }
  871.                 if (op == BPF_MUL || op == BPF_AND) {
  872.                     s->code = BPF_LD|BPF_IMM;
  873.                     val[A_ATOM] = K(s->k);
  874.                     break;
  875.                 }
  876.             }
  877.             if (vmap[val[A_ATOM]].is_const) {
  878.                 fold_op(s, val[A_ATOM], K(s->k));
  879.                 val[A_ATOM] = K(s->k);
  880.                 break;
  881.             }
  882.         }
  883.         val[A_ATOM] = F(s->code, val[A_ATOM], K(s->k));
  884.         break;
  885.  
  886.     case BPF_ALU|BPF_ADD|BPF_X:
  887.     case BPF_ALU|BPF_SUB|BPF_X:
  888.     case BPF_ALU|BPF_MUL|BPF_X:
  889.     case BPF_ALU|BPF_DIV|BPF_X:
  890.     case BPF_ALU|BPF_AND|BPF_X:
  891.     case BPF_ALU|BPF_OR|BPF_X:
  892.     case BPF_ALU|BPF_LSH|BPF_X:
  893.     case BPF_ALU|BPF_RSH|BPF_X:
  894.         op = BPF_OP(s->code);
  895.         if (alter && vmap[val[X_ATOM]].is_const) {
  896.             if (vmap[val[A_ATOM]].is_const) {
  897.                 fold_op(s, val[A_ATOM], val[X_ATOM]);
  898.                 val[A_ATOM] = K(s->k);
  899.             }
  900.             else {
  901.                 s->code = BPF_ALU|BPF_K|op;
  902.                 s->k = vmap[val[X_ATOM]].const_val;
  903.                 done = 0;
  904.                 val[A_ATOM] = 
  905.                     F(s->code, val[A_ATOM], K(s->k));
  906.             }
  907.             break;
  908.         }
  909.         /*
  910.          * Check if we're doing something to an accumulator
  911.          * that is 0, and simplify.  This may not seem like
  912.          * much of a simplification but it could open up further
  913.          * optimizations.
  914.          * XXX We could also check for mul by 1, and -1, etc.
  915.          */
  916.         if (alter && vmap[val[A_ATOM]].is_const
  917.             && vmap[val[A_ATOM]].const_val == 0) {
  918.             if (op == BPF_ADD || op == BPF_OR || 
  919.                 op == BPF_LSH || op == BPF_RSH || op == BPF_SUB) {
  920.                 s->code = BPF_MISC|BPF_TXA;
  921.                 vstore(s, &val[A_ATOM], val[X_ATOM], alter);
  922.                 break;
  923.             }
  924.             else if (op == BPF_MUL || op == BPF_DIV || 
  925.                  op == BPF_AND) {
  926.                 s->code = BPF_LD|BPF_IMM;
  927.                 s->k = 0;
  928.                 vstore(s, &val[A_ATOM], K(s->k), alter);
  929.                 break;
  930.             }
  931.             else if (op == BPF_NEG) {
  932.                 s->code = NOP;
  933.                 break;
  934.             }
  935.         }
  936.         val[A_ATOM] = F(s->code, val[A_ATOM], val[X_ATOM]);
  937.         break;
  938.  
  939.     case BPF_MISC|BPF_TXA:
  940.         vstore(s, &val[A_ATOM], val[X_ATOM], alter);
  941.         break;
  942.  
  943.     case BPF_LD|BPF_MEM:
  944.         v = val[s->k];
  945.         if (alter && vmap[v].is_const) {
  946.             s->code = BPF_LD|BPF_IMM;
  947.             s->k = vmap[v].const_val;
  948.             done = 0;
  949.         }
  950.         vstore(s, &val[A_ATOM], v, alter);
  951.         break;
  952.         
  953.     case BPF_MISC|BPF_TAX:
  954.         vstore(s, &val[X_ATOM], val[A_ATOM], alter);
  955.         break;
  956.  
  957.     case BPF_LDX|BPF_MEM:
  958.         v = val[s->k];
  959.         if (alter && vmap[v].is_const) {
  960.             s->code = BPF_LDX|BPF_IMM;
  961.             s->k = vmap[v].const_val;
  962.             done = 0;
  963.         }
  964.         vstore(s, &val[X_ATOM], v, alter);
  965.         break;
  966.  
  967.     case BPF_ST:
  968.         vstore(s, &val[s->k], val[A_ATOM], alter);
  969.         break;
  970.  
  971.     case BPF_STX:
  972.         vstore(s, &val[s->k], val[X_ATOM], alter);
  973.         break;
  974.     }
  975. }
  976.  
  977. static void
  978. deadstmt(s, last)
  979.     register struct stmt *s;
  980.     register struct stmt *last[];
  981. {
  982.     register int atom;
  983.  
  984.     atom = atomuse(s);
  985.     if (atom >= 0) {
  986.         if (atom == AX_ATOM) {
  987.             last[X_ATOM] = 0;
  988.             last[A_ATOM] = 0;
  989.         }
  990.         else
  991.             last[atom] = 0;
  992.     }
  993.     atom = atomdef(s);
  994.     if (atom >= 0) {
  995.         if (last[atom]) {
  996.             done = 0;
  997.             last[atom]->code = NOP;
  998.         }
  999.         last[atom] = s;
  1000.     }
  1001. }
  1002.  
  1003. static void
  1004. opt_deadstores(b)
  1005.     register struct block *b;
  1006. {
  1007.     register struct slist *s;
  1008.     register int atom;
  1009.     struct stmt *last[N_ATOMS];
  1010.  
  1011.     bzero((char *)last, sizeof last);
  1012.  
  1013.     for (s = b->stmts; s != 0; s = s->next)
  1014.         deadstmt(&s->s, last);
  1015.     deadstmt(&b->s, last);
  1016.  
  1017.     for (atom = 0; atom < N_ATOMS; ++atom)
  1018.         if (last[atom] && !ATOMELEM(b->out_use, atom)) {
  1019.             last[atom]->code = NOP;
  1020.             done = 0;
  1021.         }
  1022. }
  1023.  
  1024. static void
  1025. opt_blk(b, do_stmts)
  1026.     struct block *b;
  1027. {
  1028.     struct slist *s;
  1029.     struct edge *p;
  1030.     int i;
  1031.     long aval;
  1032.  
  1033.     /* 
  1034.      * Initialize the atom values.
  1035.      * If we have no predecessors, everything is undefined.
  1036.      * Otherwise, we inherent our values from our predecessors.  
  1037.      * If any register has an ambiguous value (i.e. control paths are
  1038.      * merging) give it the undefined value of 0.
  1039.      */
  1040.     p = b->in_edges;
  1041.     if (p == 0)
  1042.         bzero((char *)b->val, sizeof(b->val));
  1043.     else {
  1044.         bcopy((char *)p->pred->val, (char *)b->val, sizeof(b->val));
  1045.         while (p = p->next) {
  1046.             for (i = 0; i < N_ATOMS; ++i)
  1047.                 if (b->val[i] != p->pred->val[i])
  1048.                     b->val[i] = 0;
  1049.         }
  1050.     }
  1051.     aval = b->val[A_ATOM];
  1052.     for (s = b->stmts; s; s = s->next)
  1053.         opt_stmt(&s->s, b->val, do_stmts);
  1054.  
  1055.     /*
  1056.      * This is a special case: if we don't use anything from this
  1057.      * block, and we load the accumulator with value that is 
  1058.      * already there, eliminate all the statements.
  1059.      */
  1060.     if (do_stmts && b->out_use == 0 && aval != 0 &&
  1061.         b->val[A_ATOM] == aval)
  1062.         b->stmts = 0;
  1063.     else {
  1064.         opt_peep(b);
  1065.         opt_deadstores(b);
  1066.     }
  1067.     /*
  1068.      * Set up values for branch optimizer.
  1069.      */
  1070.     if (BPF_SRC(b->s.code) == BPF_K)
  1071.         b->oval = K(b->s.k);
  1072.     else
  1073.         b->oval = b->val[X_ATOM];
  1074.     b->et.code = b->s.code;
  1075.     b->ef.code = -b->s.code;
  1076. }
  1077.  
  1078. /*
  1079.  * Return true if any register that is used on exit from 'succ', has
  1080.  * an exit value that is different from the corresponding exit value
  1081.  * from 'b'.
  1082.  */
  1083. static int 
  1084. use_conflict(b, succ)
  1085.     struct block *b, *succ;
  1086. {
  1087.     int atom;
  1088.     atomset use = succ->out_use;
  1089.  
  1090.     if (use == 0)
  1091.         return 0;
  1092.  
  1093.     for (atom = 0; atom < N_ATOMS; ++atom)
  1094.         if (ATOMELEM(use, atom))
  1095.             if (b->val[atom] != succ->val[atom])
  1096.                 return 1;
  1097.     return 0;
  1098. }
  1099.  
  1100. struct block *
  1101. fold_edge(child, ep)
  1102.     struct block *child;
  1103.     struct edge *ep;
  1104. {
  1105.     int sense;
  1106.     int aval0, aval1, oval0, oval1;
  1107.     int code = ep->code;
  1108.  
  1109.     if (code < 0) {
  1110.         code = -code;
  1111.         sense = 0;
  1112.     } else
  1113.         sense = 1;
  1114.  
  1115.     if (child->s.code != code)
  1116.         return 0;
  1117.  
  1118.     aval0 = child->val[A_ATOM];
  1119.     oval0 = child->oval;
  1120.     aval1 = ep->pred->val[A_ATOM];
  1121.     oval1 = ep->pred->oval;
  1122.  
  1123.     if (aval0 != aval1)
  1124.         return 0;
  1125.  
  1126.     if (oval0 == oval1)
  1127.         /*
  1128.          * The operands are identical, so the 
  1129.          * result is true if a true branch was
  1130.          * taken to get here, otherwise false.
  1131.          */
  1132.         return sense ? JT(child) : JF(child);
  1133.  
  1134.     if (sense && code == (BPF_JMP|BPF_JEQ|BPF_K))
  1135.         /* 
  1136.          * At this point, we only know the comparison if we
  1137.          * came down the true branch, and it was an equility
  1138.          * comparison with a constant.  We rely on the fact that
  1139.          * distinct constants have distinct value numbers.
  1140.          */
  1141.         return JF(child);
  1142.  
  1143.     return 0;
  1144. }
  1145.  
  1146. static void
  1147. opt_j(ep)
  1148.     struct edge *ep;
  1149. {
  1150.     register int i, k;
  1151.     register struct block *target;
  1152.  
  1153.     if (JT(ep->succ) == 0)
  1154.         return;
  1155.  
  1156.     if (JT(ep->succ) == JF(ep->succ)) {
  1157.         /*
  1158.          * Common branch targets can be eliminated, provided
  1159.          * there is no data dependency.
  1160.          */
  1161.         if (!use_conflict(ep->pred, ep->succ->et.succ)) {
  1162.             done = 0;
  1163.             ep->succ = JT(ep->succ);
  1164.         }
  1165.     }
  1166.     /*
  1167.      * For each edge dominator that matches the successor of this
  1168.      * edge, promote the edge succesor to the its grandchild.
  1169.      *
  1170.      * XXX We violate the set abstraction here in favor a reasonbly
  1171.      * efficient loop.
  1172.      */
  1173.  top:
  1174.     for (i = 0; i < edgewords; ++i) {
  1175.         register u_long x = ep->edom[i];
  1176.  
  1177.         while (x != 0) {
  1178.             k = ffs(x) - 1;
  1179.             x &=~ 1 << k;
  1180.             k += i * BITS_PER_WORD;
  1181.  
  1182.             target = fold_edge(ep->succ, edges[k]);
  1183.             /*
  1184.              * Check that there is no data dependency between 
  1185.              * nodes that will be violated if we move the edge.
  1186.              */
  1187.             if (target != 0 && !use_conflict(ep->pred, target)) {
  1188.                 done = 0;
  1189.                 ep->succ = target;
  1190.                 if (JT(target) != 0)
  1191.                     /*
  1192.                      * Start over unless we hit a leaf.
  1193.                      */
  1194.                     goto top;
  1195.                 return;
  1196.             }
  1197.         }
  1198.     }
  1199. }            
  1200.  
  1201.  
  1202. static void
  1203. or_pullup(b)
  1204.     struct block *b;
  1205. {
  1206.     int val, at_top;
  1207.     struct block *pull;
  1208.     struct block **diffp, **samep;
  1209.     struct edge *ep;
  1210.  
  1211.     ep = b->in_edges;
  1212.     if (ep == 0)
  1213.         return;
  1214.  
  1215.     /*
  1216.      * Make sure each predecessor loads the same value.
  1217.      * XXX why?
  1218.      */
  1219.     val = ep->pred->val[A_ATOM];
  1220.     for (ep = ep->next; ep != 0; ep = ep->next)
  1221.         if (val != ep->pred->val[A_ATOM])
  1222.             return;
  1223.  
  1224.     if (JT(b->in_edges->pred) == b)
  1225.         diffp = &JT(b->in_edges->pred);
  1226.     else
  1227.         diffp = &JF(b->in_edges->pred);
  1228.  
  1229.     at_top = 1;
  1230.     while (1) {
  1231.         if (*diffp == 0)
  1232.             return;
  1233.  
  1234.         if (JT(*diffp) != JT(b))
  1235.             return;
  1236.  
  1237.         if (!SET_MEMBER((*diffp)->dom, b->id))
  1238.             return;
  1239.  
  1240.         if ((*diffp)->val[A_ATOM] != val)
  1241.             break;
  1242.  
  1243.         diffp = &JF(*diffp);
  1244.         at_top = 0;
  1245.     }
  1246.     samep = &JF(*diffp);
  1247.     while (1) {
  1248.         if (*samep == 0)
  1249.             return;
  1250.  
  1251.         if (JT(*samep) != JT(b))
  1252.             return;
  1253.  
  1254.         if (!SET_MEMBER((*samep)->dom, b->id))
  1255.             return;
  1256.  
  1257.         if ((*samep)->val[A_ATOM] == val)
  1258.             break;
  1259.  
  1260.         /* XXX Need to check that there are no data dependencies
  1261.            between dp0 and dp1.  Currently, the code generator
  1262.            will not produce such dependencies. */
  1263.         samep = &JF(*samep);
  1264.     }
  1265. #ifdef notdef
  1266.     /* XXX This doesn't cover everything. */
  1267.     for (i = 0; i < N_ATOMS; ++i)
  1268.         if ((*samep)->val[i] != pred->val[i])
  1269.             return;
  1270. #endif
  1271.     /* Pull up the node. */
  1272.     pull = *samep;
  1273.     *samep = JF(pull);
  1274.     JF(pull) = *diffp;
  1275.     
  1276.     /*
  1277.      * At the top of the chain, each predecessor needs to point at the
  1278.      * pulled up node.  Inside the chain, there is only one predecessor
  1279.      * to worry about.
  1280.      */
  1281.     if (at_top) {
  1282.         for (ep = b->in_edges; ep != 0; ep = ep->next) {
  1283.             if (JT(ep->pred) == b)
  1284.                 JT(ep->pred) = pull;
  1285.             else
  1286.                 JF(ep->pred) = pull;
  1287.         }
  1288.     }
  1289.     else
  1290.         *diffp = pull;
  1291.  
  1292.     done = 0;
  1293. }
  1294.     
  1295. static void
  1296. and_pullup(b)
  1297.     struct block *b;
  1298. {
  1299.     int val, at_top;
  1300.     struct block *pull;
  1301.     struct block **diffp, **samep;
  1302.     struct edge *ep;
  1303.  
  1304.     ep = b->in_edges;
  1305.     if (ep == 0)
  1306.         return;
  1307.  
  1308.     /*
  1309.      * Make sure each predecessor loads the same value.
  1310.      */
  1311.     val = ep->pred->val[A_ATOM];
  1312.     for (ep = ep->next; ep != 0; ep = ep->next)
  1313.         if (val != ep->pred->val[A_ATOM])
  1314.             return;
  1315.  
  1316.     if (JT(b->in_edges->pred) == b)
  1317.         diffp = &JT(b->in_edges->pred);
  1318.     else
  1319.         diffp = &JF(b->in_edges->pred);
  1320.  
  1321.     at_top = 1;
  1322.     while (1) {
  1323.         if (*diffp == 0)
  1324.             return;
  1325.  
  1326.         if (JF(*diffp) != JF(b))
  1327.             return;
  1328.  
  1329.         if (!SET_MEMBER((*diffp)->dom, b->id))
  1330.             return;
  1331.  
  1332.         if ((*diffp)->val[A_ATOM] != val)
  1333.             break;
  1334.  
  1335.         diffp = &JT(*diffp);
  1336.         at_top = 0;
  1337.     }
  1338.     samep = &JT(*diffp);
  1339.     while (1) {
  1340.         if (*samep == 0)
  1341.             return;
  1342.  
  1343.         if (JF(*samep) != JF(b))
  1344.             return;
  1345.  
  1346.         if (!SET_MEMBER((*samep)->dom, b->id))
  1347.             return;
  1348.  
  1349.         if ((*samep)->val[A_ATOM] == val)
  1350.             break;
  1351.  
  1352.         /* XXX Need to check that there are no data dependencies
  1353.            between diffp and samep.  Currently, the code generator
  1354.            will not produce such dependencies. */
  1355.         samep = &JT(*samep);
  1356.     }
  1357. #ifdef notdef
  1358.     /* XXX This doesn't cover everything. */
  1359.     for (i = 0; i < N_ATOMS; ++i)
  1360.         if ((*samep)->val[i] != pred->val[i])
  1361.             return;
  1362. #endif
  1363.     /* Pull up the node. */
  1364.     pull = *samep;
  1365.     *samep = JT(pull);
  1366.     JT(pull) = *diffp;
  1367.     
  1368.     /*
  1369.      * At the top of the chain, each predecessor needs to point at the
  1370.      * pulled up node.  Inside the chain, there is only one predecessor
  1371.      * to worry about.
  1372.      */
  1373.     if (at_top) {
  1374.         for (ep = b->in_edges; ep != 0; ep = ep->next) {
  1375.             if (JT(ep->pred) == b)
  1376.                 JT(ep->pred) = pull;
  1377.             else
  1378.                 JF(ep->pred) = pull;
  1379.         }
  1380.     }
  1381.     else
  1382.         *diffp = pull;
  1383.  
  1384.     done = 0;
  1385. }
  1386.  
  1387. static void
  1388. opt_blks(root, do_stmts)
  1389.     struct block *root;
  1390. {
  1391.     int i, maxlevel;
  1392.     struct block *p;
  1393.  
  1394.     init_val();
  1395.     maxlevel = root->level;
  1396.     for (i = maxlevel; i >= 0; --i)
  1397.         for (p = levels[i]; p; p = p->link)
  1398.             opt_blk(p, do_stmts);
  1399.  
  1400.     if (do_stmts)
  1401.         /* 
  1402.          * No point trying to move branches; it can't possibly
  1403.          * make a difference at this point.
  1404.          */
  1405.         return;
  1406.  
  1407.     for (i = 1; i <= maxlevel; ++i) {
  1408.         for (p = levels[i]; p; p = p->link) {
  1409.             opt_j(&p->et);
  1410.             opt_j(&p->ef);
  1411.         }
  1412.     }
  1413.     for (i = 1; i <= maxlevel; ++i) {
  1414.         for (p = levels[i]; p; p = p->link) {
  1415.             or_pullup(p);
  1416.             and_pullup(p);
  1417.         }
  1418.     }
  1419. }
  1420.  
  1421. static inline void
  1422. link_inedge(parent, child)
  1423.     struct edge *parent;
  1424.     struct block *child;
  1425. {
  1426.     parent->next = child->in_edges;
  1427.     child->in_edges = parent;
  1428. }    
  1429.  
  1430. static void
  1431. find_inedges(root)
  1432.     struct block *root;
  1433. {
  1434.     int i;
  1435.     struct block *b;
  1436.     struct edge *ep;
  1437.  
  1438.     for (i = 0; i < n_blocks; ++i)
  1439.         blocks[i]->in_edges = 0;
  1440.  
  1441.     /*
  1442.      * Traverse the graph, adding each edge to the predecessor
  1443.      * list of its sucessors.  Skip the leaves (i.e. level 0).
  1444.      */
  1445.     for (i = root->level; i > 0; --i) {
  1446.         for (b = levels[i]; b != 0; b = b->link) {
  1447.             link_inedge(&b->et, JT(b));
  1448.             link_inedge(&b->ef, JF(b));
  1449.         }
  1450.     }
  1451. }
  1452.  
  1453. static void
  1454. opt_root(b)
  1455.     struct block **b;
  1456. {
  1457.     struct slist *tmp, *s;
  1458.  
  1459.     s = (*b)->stmts;
  1460.     (*b)->stmts = 0;
  1461.     while (BPF_CLASS((*b)->s.code) == BPF_JMP && JT(*b) == JF(*b))
  1462.         *b = JT(*b);
  1463.  
  1464.     tmp = (*b)->stmts;
  1465.     if (tmp != 0)
  1466.         sappend(s, tmp);
  1467.     (*b)->stmts = s;
  1468. }
  1469.  
  1470. static void
  1471. opt_loop(root, do_stmts)
  1472.     struct block *root;
  1473.     int do_stmts;
  1474. {
  1475.     int passes = 0;
  1476. #ifdef BDEBUG
  1477.     if (dflag > 1)
  1478.         opt_dump(root);
  1479. #endif
  1480.     do {
  1481.         done = 1;
  1482.         find_levels(root);
  1483.         find_dom(root);
  1484.         find_closure(root);
  1485.         find_inedges(root);
  1486.         find_ud(root);
  1487.         find_edom(root);
  1488.         opt_blks(root, do_stmts);
  1489. #ifdef BDEBUG
  1490.         if (dflag > 1)
  1491.             opt_dump(root);
  1492. #endif
  1493.     } while (!done);
  1494. }
  1495.  
  1496. /*
  1497.  * Optimize the filter code in its dag representation.
  1498.  */
  1499. void
  1500. optimize(rootp)
  1501.     struct block **rootp;
  1502. {
  1503.     struct block *root;
  1504.  
  1505.     root = *rootp;
  1506.  
  1507.     opt_init(root);
  1508.     opt_loop(root, 0);
  1509.     opt_loop(root, 1);
  1510.     intern_blocks(root);
  1511.     opt_root(rootp);
  1512.     opt_cleanup();
  1513. }
  1514.  
  1515. static void
  1516. make_marks(p)
  1517.     struct block *p;
  1518. {
  1519.     if (!isMarked(p)) {
  1520.         Mark(p);
  1521.         if (BPF_CLASS(p->s.code) != BPF_RET) {
  1522.             make_marks(JT(p));
  1523.             make_marks(JF(p));
  1524.         }
  1525.     }
  1526. }
  1527.  
  1528. /*
  1529.  * Mark code array such that isMarked(i) is true
  1530.  * only for nodes that are alive.
  1531.  */
  1532. static void
  1533. mark_code(p)
  1534.     struct block *p;
  1535. {
  1536.     cur_mark += 1;
  1537.     make_marks(p);
  1538. }
  1539.  
  1540. /*
  1541.  * True iff the two stmt lists load the same value from the packet into
  1542.  * the accumulator.
  1543.  */
  1544. static int
  1545. eq_slist(x, y)
  1546.     struct slist *x, *y;
  1547. {
  1548.     while (1) {
  1549.         while (x && x->s.code == NOP)
  1550.             x = x->next;
  1551.         while (y && y->s.code == NOP)
  1552.             y = y->next;
  1553.         if (x == 0)
  1554.             return y == 0;
  1555.         if (y == 0)
  1556.             return x == 0;
  1557.         if (x->s.code != y->s.code || x->s.k != y->s.k)
  1558.             return 0;
  1559.         x = x->next;
  1560.         y = y->next;
  1561.     }
  1562. }
  1563.  
  1564. static inline int
  1565. eq_blk(b0, b1)
  1566.     struct block *b0, *b1;
  1567. {
  1568.     if (b0->s.code == b1->s.code &&
  1569.         b0->s.k == b1->s.k &&
  1570.         b0->et.succ == b1->et.succ && 
  1571.         b0->ef.succ == b1->ef.succ)
  1572.         return eq_slist(b0->stmts, b1->stmts);
  1573.     return 0;
  1574. }
  1575.  
  1576. static void
  1577. intern_blocks(root)
  1578.     struct block *root;
  1579. {
  1580.     struct block *p;
  1581.     int i, j;
  1582.     int done;
  1583.  top:
  1584.     done = 1;
  1585.     for (i = 0; i < n_blocks; ++i)
  1586.         blocks[i]->link = 0;
  1587.  
  1588.     mark_code(root);
  1589.  
  1590.     for (i = n_blocks - 1; --i >= 0; ) {
  1591.         if (!isMarked(blocks[i]))
  1592.             continue;
  1593.         for (j = i + 1; j < n_blocks; ++j) {
  1594.             if (!isMarked(blocks[j]))
  1595.                 continue;
  1596.             if (eq_blk(blocks[i], blocks[j])) {
  1597.                 blocks[i]->link = blocks[j]->link ?
  1598.                     blocks[j]->link : blocks[j];
  1599.                 break;
  1600.             }
  1601.         }
  1602.     }
  1603.     for (i = 0; i < n_blocks; ++i) {
  1604.         p = blocks[i];
  1605.         if (JT(p) == 0)
  1606.             continue;
  1607.         if (JT(p)->link) {
  1608.             done = 0;
  1609.             JT(p) = JT(p)->link;
  1610.         }
  1611.         if (JF(p)->link) {
  1612.             done = 0;
  1613.             JF(p) = JF(p)->link;
  1614.         }
  1615.     }
  1616.     if (!done)
  1617.         goto top;
  1618. }
  1619.  
  1620. static void
  1621. opt_cleanup()
  1622. {
  1623.     free((void *)vnode_base);
  1624.     free((void *)vmap);
  1625.     free((void *)edges);
  1626.     free((void *)space);
  1627.     free((void *)levels);
  1628.     free((void *)blocks);
  1629. }
  1630.  
  1631. /*
  1632.  * Return the number of stmts in 's'.
  1633.  */
  1634. static int
  1635. slength(s)
  1636.     struct slist *s;
  1637. {
  1638.     int n = 0;
  1639.  
  1640.     for (; s; s = s->next)
  1641.         if (s->s.code != NOP)
  1642.             ++n;
  1643.     return n;
  1644. }
  1645.  
  1646. /*
  1647.  * Return the number of nodes reachable by 'p'.
  1648.  * All nodes should be initially unmarked.
  1649.  */
  1650. static int
  1651. count_blocks(p)
  1652.     struct block *p;
  1653. {
  1654.     if (p == 0 || isMarked(p))
  1655.         return 0;
  1656.     Mark(p);
  1657.     return count_blocks(JT(p)) + count_blocks(JF(p)) + 1;
  1658. }    
  1659.  
  1660. /*
  1661.  * Do a depth first search on the flow graph, numbering the
  1662.  * the basic blocks, and entering them into the 'blocks' array.`
  1663.  */
  1664. static void
  1665. number_blks_r(p)
  1666.     struct block *p;
  1667. {
  1668.     int n;
  1669.  
  1670.     if (p == 0 || isMarked(p))
  1671.         return;
  1672.  
  1673.     Mark(p);
  1674.     n = n_blocks++;
  1675.     p->id = n;
  1676.     blocks[n] = p;
  1677.  
  1678.     number_blks_r(JT(p));
  1679.     number_blks_r(JF(p));
  1680. }
  1681.  
  1682. /*
  1683.  * Return the number of stmts in the flowgraph reachable by 'p'.
  1684.  * The nodes should be unmarked before calling.
  1685.  */
  1686. static int
  1687. count_stmts(p)
  1688.     struct block *p;
  1689. {
  1690.     int n;
  1691.  
  1692.     if (p == 0 || isMarked(p))
  1693.         return 0;
  1694.     Mark(p);
  1695.     n = count_stmts(JT(p)) + count_stmts(JF(p));
  1696.     return slength(p->stmts) + n + 1;
  1697. }
  1698.  
  1699. /*
  1700.  * Allocate memory.  All allocation is done before optimization
  1701.  * is begun.  A linear bound on the size of all data structures is computed
  1702.  * from the total number of blocks and/or statements.
  1703.  */
  1704. static void
  1705. opt_init(root)
  1706.     struct block *root;
  1707. {
  1708.     u_long *p;
  1709.     int i, n, max_stmts;
  1710.  
  1711.     /*
  1712.      * First, count the blocks, so we can malloc an array to map
  1713.      * block number to block.  Then, put the blocks into the array.
  1714.      */
  1715.     unMarkAll();
  1716.     n = count_blocks(root);
  1717.     blocks = (struct block **)malloc(n * sizeof(*blocks));
  1718.     unMarkAll();
  1719.     n_blocks = 0;
  1720.     number_blks_r(root);
  1721.  
  1722.     n_edges = 2 * n_blocks;
  1723.     edges = (struct edge **)malloc(n_edges * sizeof(*edges));
  1724.  
  1725.     /*
  1726.      * The number of levels is bounded by the number of nodes.
  1727.      */
  1728.     levels = (struct block **)malloc(n_blocks * sizeof(*levels));
  1729.  
  1730.     edgewords = n_edges / (8 * sizeof(u_long)) + 1;
  1731.     nodewords = n_blocks / (8 * sizeof(u_long)) + 1;
  1732.  
  1733.     /* XXX */
  1734.     space = (u_long *)malloc(2 * n_blocks * nodewords * sizeof(*space)
  1735.                  + n_edges * edgewords * sizeof(*space));
  1736.     p = space;
  1737.     all_dom_sets = p;
  1738.     for (i = 0; i < n; ++i) {
  1739.         blocks[i]->dom = p;
  1740.         p += nodewords;
  1741.     }
  1742.     all_closure_sets = p;
  1743.     for (i = 0; i < n; ++i) {
  1744.         blocks[i]->closure = p;
  1745.         p += nodewords;
  1746.     }
  1747.     all_edge_sets = p;
  1748.     for (i = 0; i < n; ++i) {
  1749.         register struct block *b = blocks[i];
  1750.  
  1751.         b->et.edom = p;
  1752.         p += edgewords;
  1753.         b->ef.edom = p;
  1754.         p += edgewords;
  1755.         b->et.id = i;
  1756.         edges[i] = &b->et;
  1757.         b->ef.id = n_blocks + i;
  1758.         edges[n_blocks + i] = &b->ef;
  1759.         b->et.pred = b;
  1760.         b->ef.pred = b;
  1761.     }
  1762.     max_stmts = 0;
  1763.     for (i = 0; i < n; ++i)
  1764.         max_stmts += slength(blocks[i]->stmts) + 1;
  1765.     /*
  1766.      * We allocate at most 3 value numbers per statement,
  1767.      * so this is an upper bound on the number of valnodes
  1768.      * we'll need.
  1769.      */
  1770.     maxval = 3 * max_stmts;
  1771.     vmap = (struct vmapinfo *)malloc(maxval * sizeof(*vmap));
  1772.     vnode_base = (struct valnode *)malloc(maxval * sizeof(*vmap));
  1773. }
  1774.  
  1775. /*
  1776.  * Some pointers used to convert the basic block form of the code,
  1777.  * into the array form that BPF requires.  'fstart' will point to
  1778.  * the malloc'd array while 'ftail' is used during the recursive traversal.
  1779.  */
  1780. static struct bpf_insn *fstart;
  1781. static struct bpf_insn *ftail;
  1782.  
  1783. #ifdef BDEBUG
  1784. int bids[1000];
  1785. #endif
  1786.  
  1787. static void
  1788. convert_code_r(p)
  1789.     struct block *p;
  1790. {
  1791.     struct bpf_insn *dst;
  1792.     struct slist *src;
  1793.     int slen;
  1794.     u_int off;
  1795.  
  1796.     if (p == 0 || isMarked(p))
  1797.         return;
  1798.     Mark(p);
  1799.  
  1800.     convert_code_r(JF(p));
  1801.     convert_code_r(JT(p));
  1802.  
  1803.     slen = slength(p->stmts);
  1804.     dst = ftail -= slen + 1;
  1805.  
  1806.     p->offset = dst - fstart;
  1807.  
  1808.     for (src = p->stmts; src; src = src->next) {
  1809.         if (src->s.code == NOP)
  1810.             continue;
  1811.         dst->code = (u_short)src->s.code;
  1812.         dst->k = src->s.k;
  1813.         ++dst;
  1814.     }
  1815. #ifdef BDEBUG
  1816.     bids[dst - fstart] = p->id + 1;
  1817. #endif
  1818.     dst->code = (u_short)p->s.code;
  1819.     dst->k = p->s.k;
  1820.     if (JT(p)) {
  1821.         off = JT(p)->offset - (p->offset + slen) - 1;
  1822.         if (off >= 256) 
  1823.             error("long jumps not supported");
  1824.         dst->jt = off;
  1825.         off = JF(p)->offset - (p->offset + slen) - 1;
  1826.         if (off >= 256) 
  1827.             error("long jumps not supported");
  1828.         dst->jf = off;
  1829.     }
  1830. }
  1831.     
  1832.  
  1833. /*
  1834.  * Convert flowgraph intermediate representation to the
  1835.  * BPF array representation.  Set *lenp to the number of instructions.
  1836.  */
  1837. struct bpf_insn *
  1838. icode_to_fcode(root, lenp)
  1839.     struct block *root;
  1840.     int *lenp;
  1841. {
  1842.     int n;
  1843.     struct bpf_insn *fp;
  1844.     
  1845.     unMarkAll();
  1846.     n = *lenp = count_stmts(root);
  1847.  
  1848.     fp = (struct bpf_insn *)malloc(sizeof(*fp) * n);
  1849.     bzero((char *)fp, sizeof(*fp) * n);
  1850.     fstart = fp;
  1851.     ftail = fp + n;
  1852.  
  1853.     unMarkAll();
  1854.     convert_code_r(root);
  1855.  
  1856.     return fp;
  1857. }
  1858.  
  1859. #ifdef BDEBUG
  1860. opt_dump(root)
  1861.     struct block *root;
  1862. {
  1863.     struct bpf_program f;
  1864.     
  1865.     bzero(bids, sizeof bids);
  1866.     f.bf_insns = icode_to_fcode(root, &f.bf_len);
  1867.     bpf_dump(&f, 1);
  1868.     putchar('\n');
  1869.     free((char *)f.bf_insns);
  1870. }
  1871. #endif
  1872.